package algorithm_demo.demo01;

import java.util.HashMap;
import java.util.Map;

/**
 * 中后序
 * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 *
 * @author Api
 * @date 2023/2/4 21:32
 */
public class Code28_MiddlePostorderTraversal {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }


    public static void main(String[] args) {
        int[] in = {9,3,15,20,7};
        int[] po = {9,15,7,20,3};
        System.out.println(buildTree(in, po));
    }

    public static TreeNode buildTree(int[] in, int[] po) {
        if (in ==null || po==null ||in.length!=po.length){
            return null;
        }
        // 记录中序排序，key：具体数据int值，value：下标值
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0;i<in.length;i++){
            map.put(in[i],i);
        }
        return g(po, 0, po.length-1, in, 0,in.length-1,map);
    }


    public static TreeNode g(int[] po, int L1, int R1, int[] in, int L2, int R2, Map<Integer,Integer> map){
        if (L1>R1){
            return null;
        }
        // 找到头节点，头节点是在后序的尾部
        TreeNode head = new TreeNode(po[R1]);
        if (L1==R1){
            return head;
        }
        // find为中序的下标值
        int find = map.get(po[R1]);
        //中序：L2---（find-1)的位置和后序的L1--X是个数相等的
        //X = find+L1-L2，所以它的前一个位置是find+L1-L2-1
        head.left = g(po, L1, L1+find-L2-1, in, L2, find-1, map);
        head.right = g(po, L1+find-L2, R1-1, in, find+1, R2, map);
        return head;
    }

}
